/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * @author zhong
 *
 */
public class PossibleBipartition {
	public boolean possibleBipartition(int N, int[][] dislikes) {
		int[] color = new int[N + 1];
		Map<Integer, List<Integer>> disrelation = new HashMap<>();
		for (int[] dis : dislikes) {
			int a = dis[0];
			int b = dis[1];
			addTOdisrelation(a, b, disrelation);
			addTOdisrelation(b, a, disrelation);
		}
		return BFS(color, disrelation);
	}

	private boolean BFS(int[] color, Map<Integer, List<Integer>> disrelation) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);
		color[1] = 1;
		while (!queue.isEmpty()) {
			// 已经给i着色，给i的邻居着色，并检查邻居的颜色是否和邻居的邻居有冲突
			int i = queue.poll();
			int cor = color[i];
			if (disrelation.containsKey(i)) {
				for (Integer neib : disrelation.get(i)) {
					if (color[neib] == cor) {// 邻居的颜色和当前一样，冲突
						return false;
					} else if (color[neib] == 0) {// 尚未上色
						color[neib] = 3 - cor;// 着色为正确的颜色，并进一步处理邻居
						queue.add(neib);
					}
				}
			}
		}
		return true;
	}

	private void addTOdisrelation(int a, int b, Map<Integer, List<Integer>> disrelation) {
		if (disrelation.containsKey(a)) {
			List<Integer> list = disrelation.get(a);
			list.add(b);
		} else {
			List<Integer> list = new ArrayList<>();
			list.add(b);
			disrelation.put(a, list);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int N = 4;
		int[][] dislikes = { { 1, 2 }, { 1, 3 }, { 2, 4 } };
		System.out.println(new PossibleBipartition().possibleBipartition(N, dislikes));
	}

}
